home *** CD-ROM | disk | FTP | other *** search
/ CD Ware Multimedia 1995 May / cd Ware (Juegos) Epimundo.iso / DOS / C / WLIB.ZIP / WVEC.H < prev   
Encoding:
C/C++ Source or Header  |  1993-09-07  |  17.1 KB  |  354 lines
  1. #ifndef WVecIncluded
  2. #define WVecIncluded
  3.  
  4. // copyright (c) 1992, 1993 by Paul Wheaton
  5. // 1916 Brooks #205, Missoula, MT  59801
  6. //
  7. //       phone:  (406)543-1928
  8. //  CompuServe:  72707,207
  9. //    Internet:  72707.207@CompuServe.com
  10.  
  11. /* things to add
  12.      lower bounds (in an inherited class)
  13.      Minimize() member function to make Alloc==Len
  14.      virtual memory handler (using disk)
  15.      ExtraAlloc() mem func to set how much extra is to be allocated each
  16.        time more memory is allocated (this will speed up rapidly growing
  17.        vectors)
  18.      vector sizes beyond 64k
  19. */
  20.  
  21. #include <WMisc.h>
  22.  
  23. #ifdef MAJORBBS
  24.   #include <stdlib.h>
  25. #endif
  26.  
  27. class File;
  28.  
  29. typedef const void* ConstVoidPointerType;  // xxx used to clear up cfront prob
  30.  
  31. class ByteVector
  32.   {
  33.       Byte huge* P; // pointer to first Byte in storage
  34.       long Len;   // Length of vector
  35.       long Alloc; // amount of actual storage allocated
  36.       long Extra; // amount of extra memory to allocate when getting more memory
  37.       void ReNew(long NewCapacity);
  38.       Byte huge & Ref(long Index);
  39.       friend class BitVector;
  40.       void Assign(const ByteVector& BV);
  41.       void FreeMemory();  // equivalent to new or delete
  42.       Byte Selectors(); // 16M only:  number of selectors used.  0 if using malloc
  43.       friend void DebugDisp(const ByteVector& BV);
  44.       friend class File;
  45.       friend class RecFile;
  46.       friend class ObjVec;
  47.     public:
  48.       ByteVector();
  49.       ByteVector(int);          // although these say "int", they'll be
  50.       ByteVector(int,int);      // converted to Bytes.  "int" makes for shorter
  51.       ByteVector(int,int,int);  // mangled identifiers than "Byte"
  52.       ByteVector(int,int,int,int);
  53.       ByteVector(int,int,int,int,int);
  54.       ByteVector(int,int,int,int,int,int);
  55.       ByteVector(int,int,int,int,int,int,int);
  56.       ByteVector(int,int,int,int,int,int,int,int);
  57.       ByteVector(int,int,int,int,int,int,int,int,int);
  58.       //  see the notes on the constructors at the end of this file
  59.       ByteVector(void* B, long Len);  // copy from some pointer
  60.       ByteVector(const ByteVector&);
  61.       ByteVector(File& F);  // read a ByteVector object from a file
  62.       ~ByteVector(){FreeMemory();}
  63.       void ExtraAlloc(long Quan){Extra=Quan;}
  64.         // each time more memory is needed, this is how much extra is allocated
  65.       Byte huge & operator[](long Index){return Ref(Index);}
  66.         //  To access and modify specific bytes of the vector.
  67.         //  Accessing beyond the current length will increase the vector size.
  68.         //  Completely range protected.
  69.       void operator=(const ByteVector& BV) {Assign(BV);}
  70.       Bool operator==(const ByteVector& S);
  71.       Bool operator!=(const ByteVector& S) { return !(*this==S); }
  72.       // vector concatenation
  73.       ByteVector operator+(const ByteVector& B);
  74.       ByteVector operator+(Byte B);
  75.       friend ByteVector operator+(Byte B, const ByteVector& BV);
  76.       void operator+=(const ByteVector&);
  77.       void operator+=(Byte B) {Ref(Len)=B;}
  78.       operator ConstVoidPointerType(){return P;}
  79.       void CopyTo(void* Dest, long Bytes=MaxSLong); // copy from vector to memory
  80.       void CopyFrom(void* Source, long Bytes); // copy from memory to vector
  81.       //friend void operator=(void* Dest,const ByteVector& BV) {BV.CopyTo(Dest);}
  82.       void WriteTo(File& F);  // write a ByteVector object to file
  83.       long Capacity() {return Alloc;}
  84.       long ReAlloc(long NewCapacity);
  85.       void MinimizeMemory();
  86.         // reduce memory consumption to just what is needed now
  87.       long Size() {return Len;}
  88.       long Index(Byte SearchByte, long StartIndex=0);
  89.         // returns the const NotFound if the Byte is not found in the vector
  90.         // otherwise returns the index
  91.  
  92.       Byte   operator()(long Index); // return an indexed byte.
  93.       ByteVector operator()(long Index, long Length); // return a subvector
  94.       Byte   At(long I);
  95.       ByteVector At(long Index, long Length);
  96.       ByteVector Before(long Index) {return At(0,Index);}
  97.       ByteVector Through(long Index) {return At(0,Index+1);}
  98.       ByteVector From(long Index);
  99.       ByteVector After(long Index);
  100.       void Insert(Byte C,long Index=0);
  101.       void Insert(const ByteVector& BV,long Index=0);
  102.       void Delete(long Index=0,long Length=1);
  103.       void Clear(Byte B=0); // set all elements to B
  104.       void ClearFirst(long Quan) {Ref(Quan); Clear();}
  105.         // great for initializing a vector
  106.       long Sum();
  107.       void Empty(){Len=0;}
  108.       void Clip(long NewSize);
  109.       #ifdef MAJORBBS
  110.         void* operator new(size_t size){return malloc(size);}
  111.         void  operator delete(void* p) {free(p);}
  112.       #endif
  113.   };
  114.  
  115. extern Bool BigVectorJump;
  116. /* If true, then vectors in size >64k will always be allocated in chunks of
  117. 64k.  This saves on fragmentation and recopying time. Default is True. */
  118.  
  119. const DefaultVectorExtra=16;
  120.  
  121. /*
  122.  
  123. ByteVector constructors:
  124.  
  125.   I wanted to use a variable argument constructor (see your favorite texts
  126.   on "elipsis", "...", "variable arguments" or "va_arg, va_end and
  127.   va_start") but there were limitations that I felt could lead to very hard
  128.   to find bugs, namely that the applications programmer must first pass a
  129.   value that reveals how many parameters there are.  Being off by one could
  130.   lead to a variety of problems.
  131.  
  132.   There are four ways to construct a ByteVector:
  133.  
  134.     1) ByteVector BV;
  135.  
  136.        This creates a vector that will have a length of 0 although some
  137.        memory will be allocated so that elements may be added later (which
  138.        is the most likely thing to happen).
  139.  
  140.     2) ByteVector BV(1,2,55,8);
  141.  
  142.        This creates a vector of length 4.  You may pass 1 to 9 parameters
  143.        using this type of constructors.  You're limited to 9 because the
  144.        Glock C++ name mangling mixed with MSC 5.1 limits it this way.  An
  145.        update of either of these may solve this problem.
  146.  
  147.     3) static Byte BA[]={1,2,55,8};
  148.        ByteVector BV(BA,4);
  149.  
  150.        This creates a vector of length 4, copying the elements from BA.
  151.        You don't have to copy from an array of bytes, you can use any kind
  152.        of array or even a pointer to anywhere in memory.
  153.  
  154.     4) ByteVector BV2(BV);
  155.  
  156.        Create a ByteVector from another ByteVector.
  157.  
  158. */
  159.  
  160. /*
  161.  
  162.   Note that I use the word "Atomic" in the context that it's used in the
  163.   LISP language, meaning language primitives such as int, long and float.
  164.  
  165.   The classes that are derived from ObjVec using the macros
  166.   "CreateAtomicVectorClass" or "CreateRefVectorClass"are for those types of
  167.   objects that do not need any special class constructors or destructors.
  168.   The former macro passes values through the stack as much as possible.
  169.   The latter passes pointers (as references).  They should both appear to
  170.   work the same way although there may be some differences in time and
  171.   space usage depending on your object size and how you use your vectors.
  172.  
  173.   Again, do not use objects in these vectors that cannot be bit copied,
  174.   such as class objects that contain pointers that require stack
  175.   maintenance.
  176.  
  177. */
  178.  
  179. typedef int (* CompFuncPtr)(const void*,const void*);
  180.  
  181. class ObjVec: private ByteVector
  182.   {
  183.       int  ObjSize;  // size of struct or atomic object:  2 if int, 4 if long, etc.
  184.       int  BlockSize; // see "BlockSize" at bottom of file
  185.       CompFuncPtr CFP;
  186.       void CtorHelper(int);
  187.       CompFuncPtr CurCompFunc() const;
  188.     public:
  189.       ObjVec(int ObjectSize);
  190.       ObjVec(int ObjectSize,void*);
  191.       ObjVec(int ObjectSize,void*,void*);
  192.       ObjVec(int ObjectSize,void*,void*,void*);
  193.       ObjVec(int ObjectSize,void* P, long Len);  // copy from some pointer
  194.       ObjVec(const ObjVec&);
  195.  
  196.       void ExtraAlloc(long Quan);
  197.         // when more memory is needed, how much more memory should be allocated?
  198.       void* Ref(long Index); // returns pointer to that element
  199.       operator ConstVoidPointerType() const; //{return P;}
  200.       void CopyTo(void* Dest, long Quan=MaxSLong) const; // copy from vector to memory
  201.       void CopyFrom(void* Source, long Quan); // copy to vector from memory
  202.       void WriteTo(File&) const;  // write a ObjVec object to file
  203.       long Capacity() const; // {return (Alloc/ObjSize);}
  204.       long ByteCapacity() const;
  205.       long ReAlloc(long NewCapacity);
  206.       long Size() const; // {return Len/ObjSize);}
  207.       //friend void operator=(void* Dest,const ObjVec& V);
  208.       void operator=(const ObjVec& V);// {Assign(V);}
  209.       //Bool operator==(ObjVec&);
  210.       //Bool operator!=(ObjVec& V);// { return !(*this==V); }
  211.       long Index(void* SearchObj, long StartIndex) const;
  212.       void operator+=(const ObjVec&);
  213.       ObjVec Concat(const ObjVec&) const;
  214.       ObjVec Concat(void*) const;
  215.       void AppendOneObj(void*);
  216.       ObjVec PrependOneObj(void*) const; // does not modify current obj
  217.       void Insert(const ObjVec& V,long Index=0);
  218.       void Insert(void*,long Index);
  219.       void Delete(long Index=0,long Length=1);
  220.       void Pop(){Delete(Size()-1,1);}
  221.       //void Clear(int X=0); // set all elements to X
  222.       void ClearFirst(long Quan) {Ref(Quan); Clear();}
  223.         // great for initializing a vector
  224.       long Sum() const;
  225.       void Empty(); //{Len=0;}
  226.       ObjVec At(long,long) const;
  227.       void* At(long) const;
  228.       ObjVec From(long index) const;
  229.       ObjVec After(long index) const;
  230.       void Clip(long NewSize){ByteVector::Clip(NewSize*BlockSize);}
  231.  
  232.       void SetCompFunction(void* F){CFP=(CompFuncPtr)F;}
  233.         // in BInsert(), FindE() and FindGE(), this function will be used in
  234.         // the binary search.  memcmp() will be used if this function not called
  235.       long BInsert(void* X);
  236.         // does a binary search and then inserts X.  returns index num.  if a
  237.         // dupe is found, nothing is inserted and the match index is returned.
  238.       long FindE(void* SearchObj) const;
  239.         // binary search. returns index.  returns NotFound if no exact match
  240.       long FindGE(void* SearchObj) const;
  241.         // returns NotFound if SearchObj is greater than last element
  242.       void QSort();
  243.  
  244.       #ifdef MAJORBBS
  245.         void* operator new(size_t size){return malloc(size);}
  246.         void  operator delete(void* p) {free(p);}
  247.       #endif
  248.   };
  249.  
  250. #define CreateAtomicVectorClass(ClassName,ObjType)                            \
  251. typedef int (* ObjType ## CompFuncPtr)(const ObjType*,const ObjType*);        \
  252. class ClassName:public ObjVec                                                 \
  253.   {                                                                           \
  254.     public:                                                                   \
  255.       ClassName():ObjVec(sizeof(ObjType)){}                                   \
  256.       ClassName(ObjType X):ObjVec(sizeof(ObjType),&X){}                       \
  257.       ClassName(ObjType X1, ObjType X2):ObjVec(sizeof(ObjType),&X1,&X2){}     \
  258.       ClassName(ObjType X1, ObjType X2, ObjType X3)                           \
  259.         :ObjVec(sizeof(ObjType),&X1,&X2,&X3){}                                \
  260.       ClassName(void* P, long Len):ObjVec(sizeof(ObjType),P,Len){}            \
  261.       ClassName(const ClassName& V):ObjVec(V){}                               \
  262.       ClassName(const ObjVec& V):ObjVec(V){}                                  \
  263.       ObjType& Ref(long Index) {return *(ObjType*)ObjVec::Ref(Index);}        \
  264.       ObjType& operator[](long Index){return *(ObjType*)ObjVec::Ref(Index);}  \
  265.       void operator+=(ObjType X){AppendOneObj(&X);}                           \
  266.       void operator+=(ClassName X){ObjVec::operator+=(X);}                    \
  267.       ClassName operator+(const ClassName& V){return ObjVec::Concat(V);}      \
  268.       ClassName operator+(ObjType X){return ObjVec::Concat(&X);}              \
  269.       friend ClassName operator+(ObjType X, const ClassName& V1)              \
  270.         {return V1.PrependOneObj(&X);}                                        \
  271.       long Index(ObjType SearchObj, long StartIndex=0) const                  \
  272.         {return ObjVec::Index(&SearchObj,StartIndex);}                        \
  273.       ObjType operator()(long Index) const                                    \
  274.         {return *(ObjType*)ObjVec::At(Index);}                                \
  275.       ClassName operator()(long Index, long Length) const                     \
  276.         {return ObjVec::At(Index,Length);}                                    \
  277.       ObjType At(long Index){return *(ObjType*)ObjVec::At(Index);}            \
  278.       ClassName At(long Index, long Length)                                   \
  279.         {return ObjVec::At(Index,Length);}                                    \
  280.       ClassName Before(long Index){return ObjVec::At(0,Index);}               \
  281.       ClassName Through(long Index){return ObjVec::At(0,Index+1);}            \
  282.       ClassName From(long Index){return ObjVec::From(Index);}                 \
  283.       ClassName After(long Index){return ObjVec::After(Index);}               \
  284.       void Insert(ObjType C,long Index=0){ObjVec::Insert(&C,Index);}          \
  285.       void SetCompFunction(ObjType ## CompFuncPtr CFP)                        \
  286.         {ObjVec::SetCompFunction((void*)CFP);}                                \
  287.       long BInsert(ObjType X){return ObjVec::BInsert(&X);}                    \
  288.       long FindE(ObjType X){return ObjVec::FindE(&X);}                        \
  289.       long FindGE(ObjType X){return ObjVec::FindGE(&X);}                      \
  290.   };
  291.  
  292. #define CreateRefVectorClass(ClassName,ObjType)                               \
  293. typedef int (* ObjType ## CompFuncPtr)(const ObjType*,const ObjType*);        \
  294. class ClassName:public ObjVec                                                 \
  295.   {                                                                           \
  296.     public:                                                                   \
  297.       ClassName():ObjVec(sizeof(ObjType)){}                                   \
  298.       ClassName(ObjType& X):ObjVec(sizeof(ObjType),&X){}                      \
  299.       ClassName(ObjType& X1, ObjType& X2):                                    \
  300.         ObjVec(sizeof(ObjType),&X1,&X2){}                                     \
  301.       ClassName(ObjType& X1, ObjType& X2, ObjType& X3)                        \
  302.         :ObjVec(sizeof(ObjType),&X1,&X2,&X3){}                                \
  303.       ClassName(void* P, long Len):ObjVec(sizeof(ObjType),P,Len){}            \
  304.       ClassName(const ClassName& V):ObjVec(V){}                               \
  305.       ClassName(const ObjVec& V):ObjVec(V){}                                  \
  306.       ObjType& Ref(long Index) {return *(ObjType*)ObjVec::Ref(Index);}        \
  307.       ObjType& operator[](long Index){return Ref(Index);}                     \
  308.       void operator+=(ObjType& X){AppendOneObj(&X);}                          \
  309.       void operator+=(ClassName X){ObjVec::operator+=(X);}                    \
  310.       ClassName operator+(const ClassName& V){return Concat(V);}              \
  311.       ClassName operator+(ObjType& X){return Concat(&X);}                     \
  312.       friend ClassName operator+(ObjType& X, const ClassName& V1)             \
  313.         {return V1.PrependOneObj(&X);}                                        \
  314.       long Index(ObjType& SearchObj, long StartIndex=0)                       \
  315.         {return ObjVec::Index(&SearchObj,StartIndex);}                        \
  316.       ObjType operator()(long Index) {return *(ObjType*)ObjVec::At(Index);}   \
  317.       ClassName operator()(long Index, long Length)                           \
  318.         {return ObjVec::At(Index,Length);}                                    \
  319.       ObjType At(long Index){return *(ObjType*)ObjVec::At(Index);}            \
  320.       ClassName At(long Index, long Length)                                   \
  321.         {return ObjVec::At(Index,Length);}                                    \
  322.       ClassName Before(long Index){return ObjVec::At(0,Index);}               \
  323.       ClassName Through(long Index){return ObjVec::At(0,Index+1);}            \
  324.       ClassName From(long Index){return ObjVec::From(Index);}                 \
  325.       ClassName After(long Index){return ObjVec::After(Index);}               \
  326.       void Insert(ObjType& C,long Index=0){ObjVec::Insert(&C,Index);}         \
  327.       void SetCompFunction(ObjType ## CompFuncPtr CFP)                        \
  328.         {ObjVec::SetCompFunction((void*)CFP);}                                \
  329.       long BInsert(ObjType& X){return ObjVec::BInsert(&X);}                   \
  330.       long FindE(ObjType& X){return ObjVec::FindE(&X);}                       \
  331.       long FindGE(ObjType& X){return ObjVec::FindGE(&X);}                     \
  332.   };
  333.  
  334. /*
  335.  
  336. BlockSize
  337.  
  338.   In protected mode (16M uses this) when using large chunks of memory
  339.   (beyond 64K), that represent an array of objects, the objects must occupy
  340.   a space that has a size that is a power of two (1, 2, 4, 8, 16, etc.).
  341.   This is so that a long will not lie on a 64k boundry and assignments will
  342.   be done to it (memory is not contiguous but, rather, in 64k chunks
  343.   managed by a table of contiguous pointers).
  344.  
  345.  
  346. */
  347.  
  348. CreateAtomicVectorClass(IntVector,int);
  349. CreateAtomicVectorClass(LongVector,long);
  350. CreateAtomicVectorClass(CSVector,CharStar);
  351.  
  352. #endif
  353.  
  354.